#include "heap.h"

void swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

void HPInit(HP* ph)
{
	assert(ph);
	ph->a = NULL;
	ph->size = 0;
	ph->capacity = 0;
}

void HPDestroy(HP* ph)
{
	assert(ph);
	free(ph->a);
	ph->a = NULL;
	ph->size = 0;
	ph->capacity = 0;
}

void Adjustup(HPDataType* a, int child)
{
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
		}
		else {
			break;
		}
	}
}

void HPPush(HP* ph, HPDataType x)
{
	assert(ph);
	if (ph->size == ph->capacity)
	{
		size_t newCapacity = ph->capacity == 0 ? 4 : ph->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(ph->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ph->a = tmp;
		ph->capacity = newCapacity;
	}
	ph->a[ph->size++] = x;

	Adjustup(ph->a, ph->size - 1);
}

HPDataType HPTop(HP* ph)
{
	assert(ph);

	return ph->a[0];
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 假设法，选出左右孩子中小的那个孩子
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HPPop(HP* ph)
{
	assert(ph);
	assert(ph->size > 0);

	swap(&ph->a[ph->size - 1], &ph->a[0]);
	ph->size--;
	AdjustDown(ph->a, ph->size, 0);
}


bool HPEmpty(HP* ph)
{
	assert(ph);
	return ph->size == 0;
}